package arithmetic.matrixFind;

/**
 * Created by jiangfeng on 2017/10/13. �������
 *
 * �������µ� n*n �����־���ÿ�д��������ϸ������ ÿ�е�����Ҳ���� ����� 1 2 3 3 5 6 4 8 9 ����Ҫ�����һ���㷨�� ����һ���� k �жϳ� k �Ƿ�����������С� �����㷨���Ҹ���ʱ�临�Ӷȣ������������������ģ�
 */
public class MatrixFind {

    public static void main(String[] args) {
        int[][] arr = {{1, 2, 3}, {3, 5, 6}, {4, 8, 9}};
        int result = matrixFind(arr, 2, 0, 3, 0, 3);
        System.out.println(result);
    }

    public static int matrixFind(int[][] arr, int k, int startRow, int endRow, int startCol, int endCol) {
        int length = endRow - startRow;// �������
        if (length == 0) {
            if (arr[startCol][startRow] == k) {
                return 1;
            } else {
                return 0;
            }
        }
        int i = 0; // ����ָ��
        // ��б�Խ����ҳ� ��kС�����Ǳ��Ԫ�أ���ֹ����Խ��
        while (arr[startRow + i][startCol + i] < k && (startRow + i) < length && (startCol + i) < length) {
            i++;
        }
        if (arr[startRow + i][startCol + i] == k) {
            return 1;
        } else if (startRow + i == length || startRow + i == length) {
            return 0;
        } else {
            return matrixFind(arr, k, startRow + i, endRow, startCol, startCol + i)
                + matrixFind(arr, k, startRow, startRow + i, startCol + i, endCol);
        }
    }

}
